// nfa.h
// An implementation of NFA for Unicode character matching. This file contains
// the functions that are common to implementations of Rscript's regular
// expression matching, assembler and the language.
//
// Copyright (C) 2008  Maksim Sipos <msipos@mailc.net>
//
// This file is a part of the Ripe language project.
//
// Ripe is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#ifndef R_NFA_HPP
#define R_NFA_HPP

#include "util/standard.hpp"
#include "util/utf8.hpp"
#include "adts/vector.hpp"

namespace Ripe {
  ////// NFANode
  class NFAState;

  // Types of matching classes
  enum NFAMatchClassTypeT {
    ClassAny,         // This node accepts any character (dot or '.')
    ClassSingle,      // This node accepts a single character, given in extra_1
    ClassRange,       // This node accepts a range of characters, such that
                      // extra_1 <= char <= extra_2
  };
  typedef enum NFAMatchClassTypeT NFAMatchClassType;

  // A matching class for an NFA node
  struct NFAMatchingClass {
    NFAMatchClassType type;
    UniChar extra1;
    UniChar extra2;
  };

  // A general node in an NFA. A network of NFA nodes (defined by a pointer to
  // the starting node) is the static portion of the NFA. The node structures do
  // not change inside while mathing is taking place. The dynamic portion of the
  // matching is contained in the NFAState structure.
  class NFANode {
    public:
      NFANode();

      virtual ~NFANode();

      // Activate this node in the given State.
      virtual void activate(NFAState* state);

      // An extra pointer to some node, used as a linked list when constructing a
      // regexp.
      NFANode* extra;

      // Route this node to a given node. For a CharNode this will set the next
      // node. For a split node, this will add a child to the given node.
      virtual void route(NFANode* node);

      // Is this a terminating state?
      virtual bool terminating();

      // Step this node with a UniChar "event"
      virtual void step(NFAState* state, UniChar event);
  };

  // A node that tests a UniChar and decides if it "passes".
  class NFACharNode : public NFANode {
    public:
      Vector<NFAMatchingClass> match_classes;

      // If match classes are satisfied, this node is activated.
      NFANode* next;

      // Set the next node.
      void route(NFANode* node);

      // If this is true, this node acts oppositely: it activates next if and
      // only if none of the match classes were satisfied.
      bool negative;

      void step(NFAState* state, UniChar event);
  };

  // A node that activates a number of children nodes.
  class NFASplitNode : public NFANode {
    public:
      Vector<NFANode*> children;

      // Add a child to the given node.
      void route(NFANode* node);

      // Activate this node's children.
      void activate(NFAState* state);
  };

  // A node that acts like a matching state
  class NFATermNode :public NFANode {
    public:
      int id;

      // This is a terminating state.
      bool terminating();
  };

  ////// NFAState

  class NFAState {
    public:
      // Step the States with a UniChar "event".
      void step(UniChar event);

      // Any active nodes?
      bool any();

      // Vector of nodes currently active.
      Vector<NFANode*> active_nodes;
  };
}

#endif /* R_NFA_HPP */
